/**
 * 
 */
package com.gwcloud.leetcode.interview100;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;

/**
 * @ClassName   : Leetcode0140 
 * @author      : ganwei 
 * @date        : 2020年5月28日
 * @Description : Leetcode0140 单词拆分 II
 */
public class Leetcode0140 {
	List<String> result = new ArrayList<String>();
    /**
     * -回溯算法，算超时了。。。
     */
	public List<String> wordBreak(String s, List<String> wordDict) {
	    HashSet<String> set = new HashSet<>();
	    for (int i = 0; i < wordDict.size(); i++) {
	        set.add(wordDict.get(i));
	    }
	    
		backtrace(s, set, 0, new StringBuilder(), wordDict);
		return result;
    }
	/**
	 * -回溯主体
	 */
	public void backtrace(String s, HashSet<String> set, int start, StringBuilder sb, List<String> wordDict){
		if(start == s.length()){
			result.add(sb.toString().substring(0,sb.length()-1));
			return;
		}
		for(int i = start+1; i <= s.length(); i++){
			if(!set.contains(s.substring(start, i))){
				continue;
			}
			
			sb.append(s.substring(start, i));
			sb.append(" ");
			backtrace(s,set, i, sb, wordDict);
			sb.delete(sb.length() - (i - start) - 1, sb.length());
			
		}
	}

    /**
     * -回溯算法，算超时了。。。
     */
	public List<String> wordBreak_1(String s, List<String> wordDict) {
	    HashSet<String> set = new HashSet<>();
	    for (int i = 0; i < wordDict.size(); i++) {
	        set.add(wordDict.get(i));
	    }
	    
	    return wordBreakHelper(s, set, new HashMap<String, List<String>>());
    }
	
    /**
     * -解题思路2
     */
	private List<String> wordBreakHelper(String s, HashSet<String> set, HashMap<String, List<String>> map) {
	    if (s.length() == 0) {
	        return new ArrayList<>();
	    }
	    if (map.containsKey(s)) {
	        return map.get(s);
	    }
	    
	    List<String> res = new ArrayList<>();
	    
	    for (int j = 0; j < s.length(); j++) {
	        //判断当前字符串是否存在
	        if (set.contains(s.substring(j, s.length()))) {
	            //空串的情况，直接加入
	            if (j == 0) {
	                res.add(s.substring(j, s.length()));
	            } else {
	                //递归得到剩余字符串的所有组成可能，然后和当前字符串分别用空格连起来加到结果中
	                List<String> temp = wordBreakHelper(s.substring(0, j), set, map);
	                for (int k = 0; k < temp.size(); k++) {
	                    String t = temp.get(k);
	                    res.add(t + " " + s.substring(j, s.length()));
	                }
	            }

	        }
	    }
	    //缓存结果
	    map.put(s, res);
	    return res;
	}


	/**
	 * -主函数
	 */
	public static void main(String[] args){
		Leetcode0140 l0140 = new Leetcode0140();
		String s = "";
	}
}
